package com.zcmyth;

import java.util.ArrayList;
import java.util.List;

import com.google.common.collect.Lists;

public class MergeSort {

  private static <T extends Comparable<T>> List<T> merge(List<T> list1, List<T> list2) {
    ArrayList<T> list = Lists.newArrayList();
    int index1 = 0;
    int index2 = 0;
    while (index1 < list1.size() && index2 < list2.size()) {
      if (list1.get(index1).compareTo(list2.get(index2)) <= 0) {
        list.add(list1.get(index1++));
      } else {
        list.add(list2.get(index2++));
      }
    }
    while (index1 < list1.size()) {
      list.add(list1.get(index1++));
    }
    while (index2 < list2.size()) {
      list.add(list2.get(index2++));
    }
    return list;
  }

  public static <T extends Comparable<T>> List<T> sort(List<T> list) {
    if (list.size() < 2) {
      return list;
    }
    List<List<T>> lists = Lists.partition(list, (list.size() + 1) / 2);
    return merge(sort(lists.get(0)), sort(lists.get(1)));
  }
}
